<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 统计和小于目标的下标对数目
        // 时间复杂度：O(n^3)
        // 空间复杂度：O(1)
        var triangleNumber = function(nums) {
            nums.sort((a, b) => a - b)
            let ans = 0
            let n = nums.length
            for (let k = 2; k < nums.length; k++) {
                // 下面这两点很难想到
                // 1. 规定1<=a<=b<=c,我们规定j是k-1，然后i是从0开始的往右，j从k-1开始往左
                // 2. a + b > c 只需要判断这个
                //    a + c > b 必然成立，因为 a + c > a + b
                //    b + c > a 必然成立，因为 b + c > a + a = 2a > a

                let i = 0; // a = nums[i]
                let j = k - 1; // b = nums[j]

                while (i < j) {
                    // 两边之和大于第三边，两边之差小于第三边
                    if (nums[i] + nums[j] > nums[k]) {
                        ans += j - i
                        j--
                        /* 
                            意思是：从[i, j - 1]之间的数都满足加上nums[j]大于第三边
                                如果nums[i] + nums[j]比nums[k]大，那么
                                nums[i + 1] + nums[j] > nums[k]
                                nums[i + 2] + nums[j] > nums[k]
                                nums[i + 3] + nums[j] > nums[k]
                                ……
                                nums[j - 1] + nums[j] > nums[k]
                        */
                    } else {
                        i++
                        /* 
                            意思是：nums[i]没有作用了，还不够大
                                如果nums[i] + nums[j]比nums[k]小，那么
                                nums[i] + nums[j - 1] < nums[k]
                                nums[i] + nums[j - 2] < nums[k]
                                nums[i] + nums[j - 3] < nums[k]
                                ……
                                nums[i] + nums[i+1] < nums[k]
                        */
                    }
                }
            }
            return ans
        };
        // console.log(fourSum([1, 0, -1, 0, -2, 2], 0));
        console.log(fourSum([-1,0,1,2,-1,-4], -1));
        // console.log(threeSumClosest([-1,2,1,-4], 1));
    </script>
</body>
</html>